package com.zklh.leetcode.top100;

import java.util.*;

/**
 * LRU缓存
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/9/27
 */
public class Solution146 {
    class LRUCache {

        class Node{
            int key;
            int value;
        }

        private Map<Integer, Node> map = new HashMap<>();
        private Queue<Node> queue = new LinkedList<>();
        private int capacity = 0;
        private int size = 0;

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            neaten();
            if (!map.containsKey(key)) {
                return -1;
            }
            Node oldNode = map.get(key);
            put(key, oldNode.value);
            return oldNode.value;
        }

        public void put(int key, int value) {
            if (size < capacity && !map.containsKey(key)) {
                add(key, value);
                size++;
            } else if (map.containsKey(key)) {
                Node oldNode = map.get(key);
                oldNode.key = -1;

                add(key, value);
            } else if (size == capacity) {
                neaten();
                Node oldNode = queue.poll();
                map.remove(oldNode.key);
                add(key, value);
            }
        }

        private void add(int key, int value) {
            Node node = new Node();
            node.key = key;
            node.value = value;
            map.put(key, node);
            queue.add(node);
        }

        private void neaten(){
            while (!queue.isEmpty() && queue.peek().key == -1) {
                queue.poll();
            }
        }
    }
}